package DataStructrue.math;

import java.util.*;

//数论算法
public class Maths {
    //公式 9223372036854775783L
    //等差数列:an=a1+(n-1)*d; 前n项和:Sn=a1*n+n*(n-1)*d/2=(a1+an)*n/2
    //等比数列:an=a1*q^(n-1); 前n项和:q!=1 -> Sn=a1*(q^n-1)/(q-1)=(an*q-a1)/(q-1); q=1 -> Sn=n*a1
    //平方和:n*(n+1)*(2*n+1)/6; 立方和:n^2*(n+1)^2/4
    //贝祖定理:若a,b互质,则a*x+b*y=c有无穷组整数解,x=b*k+x0,y=-a*k+y0;  扩展:若a,b互质,则两者无法组成的最大数c=a*b-a-b,可组成数与不可组成数在区间[0,c]对称
    //欧拉定理:若a,b互质,则a^f(b)=1(%b),欧拉函数f(b)=b*mul(1-1/p),其中p为b的质因数
    //费马小定理:若a,b互质,且b为质数,则a^(b-1)=1(%b),即a的逆元为a^(b-2)%b
    //约数定理:根据唯一分解定理,如果x=mul(pi^ci),则约数个数为mul(ci+1),约数之和为mul(pi^0+...+pi^ci)


    //最大公约数
    public static long gcd(long a, long b) {
        if (b == 0) return a>0?a:-a;
        return gcd(b, a % b);
    }
    //最小公倍数
    public static long lcm(long a,long b,int mod){
        a/=gcd(a,b);
        return a%mod*(b%mod)%mod;
    }
    //log2向下取整
    public static int log2(long n) {
        return Long.bitCount(Long.highestOneBit(n) - 1);
    }
    //预处理log2
    public static int[] preLog2(long n){
        return null;
    }
    //快速幂
    public static long pow(long a, long b,int mod) {
        long ans = 1;
        while (b > 0) {
            if ((b & 1)==1) ans = ans * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return ans;
    }
    //快速乘
    public static long mul(long a,long b,int mod) {
        long ans=0;
        int sign=1;
        if(b<0){
            sign=-1;
            b=-b;
        }
        while(b>0) {
            if((b&1)==1) ans=(ans+a)%mod;
            a=(a+a)%mod;
            b>>=1;
        }
        return sign*ans;
    }
    //求a*x+b*y=c或者同余方程a*x=c(%b)的特解(a,b互质)
    public static long[] GCD(long a,long b,long c) {
        if (b == 0)
            return a>0?new long[]{c,0}:new long[]{-c,0};
        long[] ans=GCD(b, a % b,c);
        long tmp=ans[0];
        ans[0]=ans[1];
        ans[1]=(tmp-a/b*ans[1]);
        return ans;
    }
    //求同余方程组x=a(%b)的通解,通解的模为lcm(b1,...,bn)
    public static long[] crt(long[] a,long[] b){
        int n=a.length;
        long[] ans=new long[]{a[0]%b[0],b[0]};
        for (int i = 1; i < n; i++) {
            long A=ans[1];
            long B=b[i];
            long C=(a[i]-ans[0])%B;
            long gcd=gcd(A,B);
            if(C%gcd!=0)
                return null;//无解
            A/=gcd;B/=gcd;C/=gcd;
            long x=GCD(A,B,C)[0]%B;
            ans[0]+=x*ans[1];
            ans[1]*=B;
            ans[0]%=ans[1];
        }
        return ans;
    }
    //逆元(mod为质数,n<mod)
    public static long inv(long n, int mod) {
        n%=mod;
        if(n==1)
            return 1;
        return (mod-mod/n)*inv(mod%n,mod)%mod;
    }
    //预处理[1,n]的逆元(mod为质数,n<mod)
    public static long[] preInv(int n, int mod){
        int len=Math.min(n+1,mod);
        long[] ans=new long[len];
        ans[1] = 1;
        for(int i = 2; i < len; i++){
            ans[i] = (mod - mod / i) * ans[mod % i] % mod;
        }
        return ans;
    }
    //质数判断
    public static boolean isPrime(long n){
        if (n == 0 || n == 1)
            return false;
        if (n == 2 || n == 3)
            return true;
        if (n % 6 != 1 && n % 6 != 5)
            return false;
        long end = (long) Math.sqrt(n);
        for (long i = 5; i <= end; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
        }
        return true;
    }
    //线性筛求[1,n]的质数
    public static List<Integer> sievePrimes(int n) {
        boolean[] noPrime = new boolean[n+1];
        List<Integer> primes=new ArrayList<>();//存储质数
        for (int i = 2; i <= n; ++i) {
            if(!noPrime[i])
                primes.add(i);
            for(int j=0;i*primes.get(j)<=n;j++){
                noPrime[i*primes.get(j)]=true;
                if(i%primes.get(j)==0) break;
            }
        }
        return primes;
    }
    //筛法求[l,r]的质数
    public static List<Integer> sievePrimes(int l,int r){
        boolean[] noPrime = new boolean[r-l+1];
        List<Integer> primes=sievePrimes(50000);
        if(l==1) noPrime[0]=true;//l==1
        for (int p : primes) {
            if(p>Math.sqrt(r)) break;
            int begin= (int) Math.ceil(l*1.0/p);
            if(begin==1) begin++;//p>l
            for (int i = begin; (long)i*p <=r ; i++) {
                noPrime[i*p-l]=true;
            }
        }
        primes.clear();
        for (int i = 0; i < noPrime.length; i++) {
            if(!noPrime[i]) primes.add(i+l);
        }
        return primes;
    }
    //线性筛求欧拉函数,即[1,n]中与n互质的个数
    public static int[] euler(int n){
        boolean[] noPrime = new boolean[n+1];
        List<Integer> primes=new ArrayList<>();//存储[1,n]的质数
        int[] ans=new int[n+1];
        ans[1]=1;
        for (int i = 2; i <= n; ++i) {
            if(!noPrime[i]){
                primes.add(i);
                ans[i]=i-1;
            }
            for(int j=0;i*primes.get(j)<=n;j++){
                int tmp=i*primes.get(j);
                noPrime[tmp]=true ;
                if(i%primes.get(j)==0){
                    ans[tmp]=ans[i]*primes.get(j);
                    break;
                }
                ans[tmp]=ans[i]*(primes.get(j)-1);
            }
        }
        return ans;
    }
    //分解因数
    public static List<long[]> fac(long n){
        List<long[]> ans=new ArrayList<>();
        for (long i = 1; i*i <=n ; i++) {
            if(n%i==0) ans.add(new long[]{i,n/i});
        }
        return ans;
    }
    //分解质因数,及其对应数量
    public static Map<Long,Long> primeFac(long a,long b){
        Map<Long,Long> ans=new HashMap<>();
        for(long i = 2; i*i <= a; i++){
            if(a % i != 0) continue;
            long num = 0;
            while(a % i == 0){
                a /= i;
                num+=b;
            }
            ans.put(i,num);
        }
        if(a > 1) ans.put(a,b);//最后一个质因数
        return ans;
    }
    //约数个数
    public static long numFac(long a,long b){
        long ans=1;
        for(long i = 2; i*i <= a; i++){
            //如果i为n的合因数,n一定不能整除,因为i一定由之前的质因数组成,n此时已经除掉之前的所有质因数
            if(a % i != 0) continue;
            long num = 0;//质因数数量
            while(a % i == 0){
                a /= i;
                num+=b;
            }
            ans*=num+1;
        }
        if(a > 1) ans*=b+1;//最后一个质因数
        return ans;
    }
    //预处理[1,n]约数个数
    public static int[] preNumFac(int n){
        boolean[] noPrime = new boolean[n+1];
        List<Integer> primes=new ArrayList<>();//存储质数
        int[] ans=new int[n+1];//约数个数
        int[] num=new int[n+1];//最小质因子个数
        ans[1]=1;
        for (int i = 2; i <= n; ++i) {
            if(!noPrime[i]){
                primes.add(i);
                ans[i]=2;
                num[i]=1;
            }
            for(int j=0;j<primes.size()&&i*primes.get(j)<=n;j++){
                int tmp=i*primes.get(j);
                noPrime[tmp]=true;
                if(i%primes.get(j)==0) {
                    num[tmp]=num[i]+1;
                    ans[tmp]=ans[i]/(tmp)*(num[tmp]+1);
                    break;
                }
                ans[tmp]=ans[i]*2;
                num[tmp]=1;
            }
        }
        return ans;
    }
    //约数和
    public static long sumFac(long a,long b){

        return 0;
    }
    //预处理[1,n]约数和
    public static long[] preSumFac(int n){
        boolean[] noPrime = new boolean[n+1];
        List<Integer> primes=new ArrayList<>();//存储质数
        long[] ans=new long[n+1];
        long[] sum=new long[n+1];//sum(p^0+...+p^ci),其中p为最小质因子
        ans[1]=1;sum[1]=1;
        for (int i = 2; i <= n; ++i) {
            if(!noPrime[i]){
                primes.add(i);
                ans[i]=i+1;
                sum[i]=i+1;
            }
            for(int j=0;j<primes.size()&&i*primes.get(j)<=n;j++){
                int tmp=i*primes.get(j);
                noPrime[tmp]=true;
                if(i%primes.get(j)==0) {
                    sum[tmp]=sum[i]*primes.get(j)+1;
                    ans[tmp]=ans[i]/sum[i]*sum[tmp];
                    break;
                }
                ans[tmp]=ans[i]*ans[primes.get(j)];
                sum[tmp]=primes.get(j)+1;
            }
        }
        return ans;
    }
    //整数分块,区间内的商相等
    public static List<long[]> partition(long n){
        List<long[]> ans=new ArrayList<>();
        for (long l = 1, r = 0; l < n; l = r + 1) {
            r = n / (n / l);
            ans.add(new long[]{l, r});
        }
        return ans;
    }
    //日期有效判断
    public static boolean dateValid(int y,int m,int d){
        int[] days={31,28,31,30,31,30,31,31,30,31,30,31};
        if(y%400==0||y%100!=0&&y%4==0)
            days[1]++;
        return m >= 1 && m <= 12 && d >= 1 && d <= days[m - 1];
    }
    //一年中的第几天
    public static int dayOfYear(int y,int m,int d){
        int[] days={31,28,31,30,31,30,31,31,30,31,30,31};
        if(y%400==0||y%100!=0&&y%4==0)
            days[1]++;
        int ans=0;
        for (int i = 0; i < m-1; ++i) {
            ans+=days[i];
        }
        return ans+d;
    }
    //分数计算
    public static long[] fraction(long a,long b,long c,long d,int op){
        long[] ans=new long[2];
        if(op<=2){//加减法
            if(op==2) c=-c;
            ans[0]=a*d+c*b;
            ans[1]=b*d;
        }else if(op==3){//乘法
            ans[0]=a*c;
            ans[1]=b*d;
        }else{//除法
            ans[0]=a*d;
            ans[1]=c*b;
        }
        long gcd=gcd(ans[0],ans[1]);
        ans[0]/=gcd;ans[1]/=gcd;
        return ans;
    }
    //叉乘,判断
    public static long cross(long[] p, long[] q, long[] r) {
        return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
    }

}
